package com.zlsy.learning.leetcode.queue.q239;

import java.util.ArrayDeque;

/**
 * @author zhouliang
 * @date 2020/8/18 8:26
 */
public class MaxSlidingWindow1 {

  /** 双端队列：最大值放在队列头 */
  ArrayDeque<Integer> deq = new ArrayDeque<Integer>();

  int[] nums;

  public void clean_deque(int i, int k) {
    if (!deq.isEmpty() && deq.getFirst() == i - k) {
      deq.removeFirst();
    }

    /** 如果当前的值大于双端队列里面尾部的值，则移除尾部 */
    while (!deq.isEmpty() && nums[i] > nums[deq.getLast()]) {
      deq.removeLast();
    }
  }

  public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n * k == 0) {
      return new int[0];
    }
    if (k == 1) {
      return nums;
    }

    this.nums = nums;
    /** 先初始化最大的值为第一个索引 */
    int max_idx = 0;
    for (int i = 0; i < k; i++) {
      /** 当前的值是否为最大，是最大就一次从双端队列的尾部依次移除元素 */
      clean_deque(i, k);
      /** 然后把当前的元素放到队列尾部 */
      deq.addLast(i);
      if (nums[i] > nums[max_idx]) {
        max_idx = i;
      }
    }
    int[] output = new int[n - k + 1];
    output[0] = nums[max_idx];

    /** 同上 */
    for (int i = k; i < n; i++) {
      clean_deque(i, k);
      deq.addLast(i);
      output[i - k + 1] = nums[deq.getFirst()];
    }
    return output;
  }
}
